<!DOCTYPE html>
<html class="writer-html5" lang="en" >
<head>
    <meta charset="utf-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
      <link rel="shortcut icon" href="../../img/favicon.ico" />
    <title>函数 - 咩咩的笔记</title>
    <link rel="stylesheet" href="../../css/theme.css" />
    <link rel="stylesheet" href="../../css/theme_extra.css" />
        <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/10.5.0/styles/github.min.css" />
    
      <script>
        // Current page data
        var mkdocs_page_name = "\u51fd\u6570";
        var mkdocs_page_input_path = "\u79bb\u6563\u6570\u5b66\\7-\u51fd\u6570.md";
        var mkdocs_page_url = null;
      </script>
    
    <script src="../../js/jquery-3.6.0.min.js" defer></script>
    <!--[if lt IE 9]>
      <script src="../../js/html5shiv.min.js"></script>
    <![endif]-->
      <script src="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/10.5.0/highlight.min.js"></script>
      <script>hljs.initHighlightingOnLoad();</script> 
</head>

<body class="wy-body-for-nav" role="document">

  <div class="wy-grid-for-nav">
    <nav data-toggle="wy-nav-shift" class="wy-nav-side stickynav">
    <div class="wy-side-scroll">
      <div class="wy-side-nav-search">
          <a href="../.." class="icon icon-home"> 咩咩的笔记
        </a><div role="search">
  <form id ="rtd-search-form" class="wy-form" action="../../search.html" method="get">
      <input type="text" name="q" placeholder="Search docs" aria-label="Search docs" title="Type search term here" />
  </form>
</div>
      </div>

      <div class="wy-menu wy-menu-vertical" data-spy="affix" role="navigation" aria-label="Navigation menu">
              <ul>
                <li class="toctree-l1"><a class="reference internal" href="../..">主页</a>
                </li>
              </ul>
              <p class="caption"><span class="caption-text">笔记</span></p>
              <ul class="current">
                  <li class="toctree-l1"><a class="reference internal" href="#">线性代数</a>
    <ul>
                <li class="toctree-l2"><a class="reference internal" href="../../%E7%BA%BF%E6%80%A7%E4%BB%A3%E6%95%B0/0-%E5%89%8D%E8%A8%80/">0-前言</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E7%BA%BF%E6%80%A7%E4%BB%A3%E6%95%B0/1-%E7%BA%BF%E6%80%A7%E6%96%B9%E7%A8%8B%E7%BB%84/">1-线性方程组</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E7%BA%BF%E6%80%A7%E4%BB%A3%E6%95%B0/2-%E7%9F%A9%E9%98%B5%E4%BB%A3%E6%95%B0/">2-矩阵代数</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E7%BA%BF%E6%80%A7%E4%BB%A3%E6%95%B0/3-%E8%A1%8C%E5%88%97%E5%BC%8F/">3-行列式</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E7%BA%BF%E6%80%A7%E4%BB%A3%E6%95%B0/4-%E5%90%91%E9%87%8F%E7%A9%BA%E9%97%B4/">4-向量空间</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E7%BA%BF%E6%80%A7%E4%BB%A3%E6%95%B0/5-%E7%89%B9%E5%BE%81%E5%80%BC%E4%B8%8E%E7%89%B9%E5%BE%81%E5%90%91%E9%87%8F/">5-特征值与特征向量</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E7%BA%BF%E6%80%A7%E4%BB%A3%E6%95%B0/6-%E6%AD%A3%E4%BA%A4%E6%80%A7%E4%B8%8E%E6%9C%80%E5%B0%8F%E4%BA%8C%E4%B9%98/">6-正交性与最小二乘</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E7%BA%BF%E6%80%A7%E4%BB%A3%E6%95%B0/7-%E5%AF%B9%E7%A7%B0%E9%98%B5%E4%B8%8E%E4%BA%8C%E6%AC%A1%E5%9E%8B/">7-对称阵与二次型</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E7%BA%BF%E6%80%A7%E4%BB%A3%E6%95%B0/8-%E5%90%91%E9%87%8F%E7%A9%BA%E9%97%B4%E7%9A%84%E5%87%A0%E4%BD%95/">8-向量空间的几何</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E7%BA%BF%E6%80%A7%E4%BB%A3%E6%95%B0/%E9%99%84%E5%BD%95A-3Blue1Brown%E7%AC%94%E8%AE%B0/">附录A-3Blue1Brown笔记</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E7%BA%BF%E6%80%A7%E4%BB%A3%E6%95%B0/%E9%99%84%E5%BD%95B-%E9%9B%B6%E7%A9%BA%E9%97%B4%E4%B8%8E%E5%88%97%E7%A9%BA%E9%97%B4%E7%9A%84%E5%AF%B9%E6%AF%94/">附录B-零空间与列空间的对比</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E7%BA%BF%E6%80%A7%E4%BB%A3%E6%95%B0/%E9%99%84%E5%BD%95C-%E9%80%86%E7%9F%A9%E9%98%B5%E5%AE%9A%E7%90%86/">附录C-逆矩阵定理</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E7%BA%BF%E6%80%A7%E4%BB%A3%E6%95%B0/%E9%99%84%E5%BD%95D-%E6%80%9D%E7%BB%B4%E5%AF%BC%E5%9B%BE/">附录D-思维导图</a>
                </li>
    </ul>
                  </li>
                  <li class="toctree-l1"><a class="reference internal" href="#">数字电路</a>
    <ul>
                <li class="toctree-l2"><a class="reference internal" href="../../%E6%95%B0%E5%AD%97%E7%94%B5%E8%B7%AF/1.%20%E4%BB%8B%E7%BB%8D/">介绍</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E6%95%B0%E5%AD%97%E7%94%B5%E8%B7%AF/2.%20%E6%95%B0%E5%AD%97%E7%B3%BB%E7%BB%9F%E3%80%81%E8%BF%90%E7%AE%97%E5%92%8C%E7%BC%96%E7%A0%81/">数字系统、运算和编码</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E6%95%B0%E5%AD%97%E7%94%B5%E8%B7%AF/3.%20%E9%80%BB%E8%BE%91%E9%97%A8/">逻辑门</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E6%95%B0%E5%AD%97%E7%94%B5%E8%B7%AF/4.%20%E5%B8%83%E5%B0%94%E4%BB%A3%E6%95%B0/">布尔代数</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E6%95%B0%E5%AD%97%E7%94%B5%E8%B7%AF/5.%20%E7%BB%84%E5%90%88%E9%80%BB%E8%BE%91%E5%88%86%E6%9E%90/">组合逻辑分析</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E6%95%B0%E5%AD%97%E7%94%B5%E8%B7%AF/6.%20%E7%BB%84%E5%90%88%E9%80%BB%E8%BE%91%E5%8A%9F%E8%83%BD%E6%A8%A1%E5%9D%97/">组合逻辑功能模块</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E6%95%B0%E5%AD%97%E7%94%B5%E8%B7%AF/7.%20%E9%94%81%E5%AD%98%E5%99%A8%E3%80%81%E8%A7%A6%E5%8F%91%E5%99%A8%E5%92%8C%E5%AE%9A%E6%97%B6%E5%99%A8/">锁存器、触发器和定时器</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E6%95%B0%E5%AD%97%E7%94%B5%E8%B7%AF/8.%20%E7%A7%BB%E4%BD%8D%E5%AF%84%E5%AD%98%E5%99%A8/">移位寄存器</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E6%95%B0%E5%AD%97%E7%94%B5%E8%B7%AF/9.%20%E8%AE%A1%E6%95%B0%E5%99%A8/">计数器</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E6%95%B0%E5%AD%97%E7%94%B5%E8%B7%AF/10.%20%E5%82%A8%E5%AD%98%E5%99%A8/">储存器</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E6%95%B0%E5%AD%97%E7%94%B5%E8%B7%AF/11.%20%E6%A8%A1%E6%95%B0%E8%BD%AC%E6%8D%A2/">模数转换</a>
                </li>
    </ul>
                  </li>
                  <li class="toctree-l1 current"><a class="reference internal current" href="#">离散数学</a>
    <ul class="current">
                <li class="toctree-l2"><a class="reference internal" href="../2-%E5%91%BD%E9%A2%98%E9%80%BB%E8%BE%91/">命题逻辑</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../3-%E4%B8%80%E9%98%B6%E9%80%BB%E8%BE%91/">一阶逻辑</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../4-%E8%AF%81%E6%98%8E%E6%96%B9%E6%B3%95/">证明方法</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../5-%E9%9B%86%E5%90%88/">集合</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../6-%E5%85%B3%E7%B3%BB/">关系</a>
                </li>
                <li class="toctree-l2 current"><a class="reference internal current" href="./">函数</a>
    <ul class="current">
    <li class="toctree-l3"><a class="reference internal" href="#_2">基本知识</a>
        <ul>
    <li class="toctree-l4"><a class="reference internal" href="#_3">基本概念</a>
    </li>
    <li class="toctree-l4"><a class="reference internal" href="#_4">函数的性质</a>
    </li>
    <li class="toctree-l4"><a class="reference internal" href="#_5">函数运算与函数的性质</a>
    </li>
        </ul>
    </li>
    <li class="toctree-l3"><a class="reference internal" href="#_6">函数的增长与算法效率分析</a>
        <ul>
    <li class="toctree-l4"><a class="reference internal" href="#_7">函数的增长</a>
    </li>
    <li class="toctree-l4"><a class="reference internal" href="#_8">算法效率分析基础</a>
    </li>
    <li class="toctree-l4"><a class="reference internal" href="#_9">算法复杂度基础知识</a>
    </li>
        </ul>
    </li>
    </ul>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../8-%E8%AE%A1%E6%95%B0%E4%B8%8E%E7%BB%84%E5%90%88/">计数与组合</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../9-%E5%9B%BE%E4%B8%8E%E6%A0%91/">图与树</a>
                </li>
    </ul>
                  </li>
                  <li class="toctree-l1"><a class="reference internal" href="#">计算机组成原理</a>
    <ul>
                <li class="toctree-l2"><a class="reference internal" href="../../%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86/1.%20%E8%AE%A1%E7%AE%97%E6%9C%BA%E6%A6%82%E8%A7%88/">计算机概览</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86/2.%20%E6%8C%87%E4%BB%A4/">指令</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86/3.%20%E8%AE%A1%E7%AE%97%E6%9C%BA%E4%B8%AD%E7%9A%84%E8%BF%90%E7%AE%97/">计算机中的运算</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86/4.%20MIPS%20CPU%E8%AE%BE%E8%AE%A1/">MIPS CPU设计</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86/5.%20%E5%AD%98%E5%82%A8%E5%99%A8%E5%B1%82%E6%AC%A1%E7%BB%93%E6%9E%84/">存储器层次结构</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86/6.%20%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%B3%BB%E7%BB%9F%E6%80%BB%E7%BA%BF/">计算机系统总线</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86/7.%20%E8%BE%93%E5%85%A5%E8%BE%93%E5%87%BA%E7%B3%BB%E7%BB%9F/">输入输出系统</a>
                </li>
    </ul>
                  </li>
                  <li class="toctree-l1"><a class="reference internal" href="#">计算机组成原理实验</a>
    <ul>
                <li class="toctree-l2"><a class="reference internal" href="../../%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86%E5%AE%9E%E9%AA%8C/1/1/">加法器</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86%E5%AE%9E%E9%AA%8C/2/2/">有限状态机</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86%E5%AE%9E%E9%AA%8C/3/3/">MIPS指令集1</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86%E5%AE%9E%E9%AA%8C/4/4/">MIPS指令集2</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86%E5%AE%9E%E9%AA%8C/5/5/">存储器实验</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86%E5%AE%9E%E9%AA%8C/6/6/">寄存器堆与 ALU 设计实验</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86%E5%AE%9E%E9%AA%8C/7/7/">存储器与控制器实验</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86%E5%AE%9E%E9%AA%8C/8/8/">单周期处理器实验</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86%E5%AE%9E%E9%AA%8C/9/9/">多周期处理器实验</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86%E5%AE%9E%E9%AA%8C/10/10/">多周期处理器综合性开放实验</a>
                </li>
    </ul>
                  </li>
                  <li class="toctree-l1"><a class="reference internal" href="#">概率论</a>
    <ul>
                <li class="toctree-l2"><a class="reference internal" href="../../%E6%A6%82%E7%8E%87%E8%AE%BA/1.%20%E6%A6%82%E7%8E%87%E8%AE%BA%E7%9A%84%E5%9F%BA%E6%9C%AC%E6%A6%82%E5%BF%B5/">概率论的基本概念</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E6%A6%82%E7%8E%87%E8%AE%BA/2.%20%E9%9A%8F%E6%9C%BA%E5%8F%98%E9%87%8F%E5%8F%8A%E5%85%B6%E5%88%86%E5%B8%83/">随机变量及其分布</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E6%A6%82%E7%8E%87%E8%AE%BA/3.%20%E5%A4%9A%E7%BB%B4%E9%9A%8F%E6%9C%BA%E5%8F%98%E9%87%8F%E5%8F%8A%E5%85%B6%E5%88%86%E5%B8%83/">多维随机变量及其分布</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E6%A6%82%E7%8E%87%E8%AE%BA/4.%20%E9%9A%8F%E6%9C%BA%E5%8F%98%E9%87%8F%E7%9A%84%E6%95%B0%E5%AD%97%E7%89%B9%E5%BE%81/">随机变量的数字特征</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E6%A6%82%E7%8E%87%E8%AE%BA/5.%20%E5%A4%A7%E6%95%B0%E5%AE%9A%E5%BE%8B%E5%8F%8A%E4%B8%AD%E5%BF%83%E6%9E%81%E9%99%90%E5%AE%9A%E7%90%86/">大数定律及中心极限定理</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E6%A6%82%E7%8E%87%E8%AE%BA/6.%20%E6%A0%B7%E6%9C%AC%E5%8F%8A%E6%8A%BD%E6%A0%B7%E5%88%86%E5%B8%83/">样本及抽样分布</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E6%A6%82%E7%8E%87%E8%AE%BA/7.%20%E5%8F%82%E6%95%B0%E4%BC%B0%E8%AE%A1/">参数估计</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E6%A6%82%E7%8E%87%E8%AE%BA/8.%20%E5%81%87%E8%AE%BE%E9%AA%8C%E8%AF%81/">假设验证</a>
                </li>
    </ul>
                  </li>
                  <li class="toctree-l1"><a class="reference internal" href="#">信号与系统</a>
    <ul>
                <li class="toctree-l2"><a class="reference internal" href="../../%E4%BF%A1%E5%8F%B7%E4%B8%8E%E7%B3%BB%E7%BB%9F/1.%20%E4%BF%A1%E5%8F%B7%E4%B8%8E%E7%B3%BB%E7%BB%9F/">信号与系统</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E4%BF%A1%E5%8F%B7%E4%B8%8E%E7%B3%BB%E7%BB%9F/2.%20%E7%BA%BF%E6%80%A7%E6%97%B6%E4%B8%8D%E5%8F%98%E7%B3%BB%E7%BB%9F/">线性时不变系统</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E4%BF%A1%E5%8F%B7%E4%B8%8E%E7%B3%BB%E7%BB%9F/3.%20%E5%91%A8%E6%9C%9F%E4%BF%A1%E5%8F%B7%E7%9A%84%E5%82%85%E9%87%8C%E5%8F%B6%E7%BA%A7%E6%95%B0%E8%A1%A8%E7%A4%BA/">周期信号的傅里叶级数表示</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E4%BF%A1%E5%8F%B7%E4%B8%8E%E7%B3%BB%E7%BB%9F/4.%20%E8%BF%9E%E7%BB%AD%E6%97%B6%E9%97%B4%E5%82%85%E9%87%8C%E5%8F%B6%E5%8F%98%E6%8D%A2/">连续时间傅里叶变换</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E4%BF%A1%E5%8F%B7%E4%B8%8E%E7%B3%BB%E7%BB%9F/5.%20%E7%A6%BB%E6%95%A3%E6%97%B6%E9%97%B4%E5%82%85%E9%87%8C%E5%8F%B6%E5%8F%98%E6%8D%A2/">离散时间傅里叶变换</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E4%BF%A1%E5%8F%B7%E4%B8%8E%E7%B3%BB%E7%BB%9F/6.%20%E4%BF%A1%E5%8F%B7%E4%B8%8E%E7%B3%BB%E7%BB%9F%E7%9A%84%E6%97%B6%E5%9F%9F%E5%92%8C%E9%A2%91%E5%9F%9F%E7%89%B9%E6%80%A7/">信号与系统的时域和频域特性</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E4%BF%A1%E5%8F%B7%E4%B8%8E%E7%B3%BB%E7%BB%9F/7.%20%E9%87%87%E6%A0%B7/">采样</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E4%BF%A1%E5%8F%B7%E4%B8%8E%E7%B3%BB%E7%BB%9F/9.%20%E6%8B%89%E6%99%AE%E6%8B%89%E6%96%AF%E5%8F%98%E6%8D%A2/">拉普拉斯变换</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E4%BF%A1%E5%8F%B7%E4%B8%8E%E7%B3%BB%E7%BB%9F/10.%20z%E5%8F%98%E6%8D%A2/">z变换</a>
                </li>
    </ul>
                  </li>
              </ul>
      </div>
    </div>
    </nav>

    <section data-toggle="wy-nav-shift" class="wy-nav-content-wrap">
      <nav class="wy-nav-top" role="navigation" aria-label="Mobile navigation menu">
          <i data-toggle="wy-nav-top" class="fa fa-bars"></i>
          <a href="../..">咩咩的笔记</a>
        
      </nav>
      <div class="wy-nav-content">
        <div class="rst-content"><div role="navigation" aria-label="breadcrumbs navigation">
  <ul class="wy-breadcrumbs">
    <li><a href="../.." class="icon icon-home" aria-label="Docs"></a> &raquo;</li>
          <li>笔记 &raquo;</li>
          <li>离散数学 &raquo;</li>
      <li>函数</li>
    <li class="wy-breadcrumbs-aside">
    </li>
  </ul>
  <hr/>
</div>
          <div role="main" class="document" itemscope="itemscope" itemtype="http://schema.org/Article">
            <div class="section" itemprop="articleBody">
              
                <h1 id="_1">函数</h1>
<p>离散数学中的函数强调其建立了两个几何元素之间的某种对应</p>
<h2 id="_2">基本知识</h2>
<h3 id="_3">基本概念</h3>
<ul>
<li>
<p>（定义7.1）集合A到B的<strong>函数</strong>，记为<span class="arithmatex">\(f:A\to B\)</span>，是笛卡尔积<span class="arithmatex">\(A\times B\)</span>的子集，且满足对任意<span class="arithmatex">\(a\in A\)</span>都有且仅有唯一的<span class="arithmatex">\(b\in B\)</span>使得<span class="arithmatex">\(\langle a,b\rangle\in f\)</span>。由于b存在且唯一，因此记为<span class="arithmatex">\(b=f(a)\)</span>，并称b是a在函数f下的<strong>像</strong>，而a是b在函数f下的的<strong>原像</strong>。上下文明确时可以将f省略而直接说b是a的像/a是b的原像。</p>
</li>
<li>
<p>（定义7.2）对于函数<span class="arithmatex">\(f:A\to B\)</span>，称A是f的<strong>定义域</strong>或简称<strong>域</strong>，B是f的<strong>陪域</strong>；定义<span class="arithmatex">\(S\subseteq A\)</span>在<span class="arithmatex">\(f\)</span>下的<strong>像集</strong>为<span class="arithmatex">\(f(S)=\{y\in B\mid\exists x\in S,y=f(x)\}\subseteq B\)</span>，<span class="arithmatex">\(T\subseteq B\)</span>在<span class="arithmatex">\(f\)</span>下的<strong>逆像集</strong>为<span class="arithmatex">\(f^{-1}(T)\)</span>；特别的，称f(A)是f的<strong>值域</strong>，记为<strong>ran(f)</strong></p>
</li>
<li>
<p>常见函数</p>
<ol>
<li>以空集为定义域的函数称为<strong>空函数</strong></li>
<li>任意非空集A上的恒等关系<span class="arithmatex">\(\Delta_A\)</span>称为A的<strong>恒等函数</strong>，记作<strong>id</strong><span class="arithmatex">\(_A\)</span></li>
<li>设U是全集，S是U的子集，定义S上的<strong>特征函数</strong><span class="arithmatex">\(X_s:U\to 2,2=\{0,1\}\)</span>，若x在S中则<span class="arithmatex">\(X_s(x)=1\)</span>，否则<span class="arithmatex">\(X_s(x)=0\)</span></li>
<li>设R是非空集A上的等价关系，定义<strong>自然函数</strong><span class="arithmatex">\(\rho:A\to A/R,\rho(a)=[a]_R\)</span></li>
<li>设<span class="arithmatex">\((A,\preceq)\)</span>和<span class="arithmatex">\((B,\preccurlyeq)\)</span>是两个偏序集，定义函数<span class="arithmatex">\(f:A\to B\)</span>的<strong>单调递增</strong>性质指对A中的任意两个元素a,b，如果<span class="arithmatex">\(a\preceq b\)</span>则<span class="arithmatex">\(f(a)\preccurlyeq f(b)\)</span></li>
</ol>
</li>
<li>
<p>函数又称<strong>映射</strong>，符合定义7.1的函数称为<strong>全函数</strong>，如果存在A中的某个元素无法对应到B中的元素，则这种函数称为<strong>偏函数</strong>。本书不讨论偏函数。</p>
</li>
</ul>
<h3 id="_4">函数的性质</h3>
<ul>
<li>
<p>设<span class="arithmatex">\(f:A\to B\)</span>是函数</p>
<ol>
<li>如果<span class="arithmatex">\(\forall x,y\in A,f(x)=f(y)\to x=y\)</span>，也就是说B中每个元素至多对应A中的一个元素，则f是<strong>单函数</strong>（单射）</li>
<li>如果<span class="arithmatex">\(ran(f)=B\)</span>，也就是说B中的每个元素至少对应A中的一个元素，则f是<strong>满函数</strong>（满射）</li>
<li>如果f既单射又满射，则f是<strong>双函数</strong>（双射）<blockquote>
<p>只有A的元素数量大于等于B，函数才可能是满射，A的元素数量小于等于B函数才可能是单射，A的元素等于B，函数才可能是双射</p>
</blockquote>
</li>
</ol>
</li>
<li>
<p>多元函数可以看做A是有序对集合的函数，有序对的尖括号在无歧义时省略</p>
</li>
</ul>
<h3 id="_5">函数运算与函数的性质</h3>
<p>集合运算对函数不适用，所以函数运算主要有复合和求逆</p>
<ul>
<li>
<p>（定义7.4）函数<span class="arithmatex">\(f:A\to B\)</span>和<span class="arithmatex">\(g:B\to C\)</span>的<strong>复合</strong>，记为<span class="arithmatex">\(g\circ f\)</span>，定义为<span class="arithmatex">\(\forall x\in A,(g\circ f)(x)=g(f(x))\)</span></p>
<blockquote>
<p>函数复合运算等价于关系复合运算</p>
</blockquote>
</li>
<li>
<p>（定理7.1）</p>
<ol>
<li>函数复合满足结合律：设函数<span class="arithmatex">\(f:A\to B,g:B\to C,h:C\to D\)</span>，有<span class="arithmatex">\(h\circ(g\circ h)=(h\circ g)\circ f\)</span></li>
<li>恒等关系是函数复合的单位元：<span class="arithmatex">\(id_B\circ f=f\circ id_A\)</span></li>
</ol>
</li>
<li>
<p>（定理7.2）函数复合保持单射、满射和双射的性质</p>
</li>
<li>
<p>（定义7.5）设<span class="arithmatex">\(f:A\to B\)</span>是双函数，则它的逆关系<span class="arithmatex">\(f^{-1}\)</span>也是函数，称为f的<strong>逆函数</strong>或<strong>反函数</strong></p>
</li>
<li>
<p>（定理7.3）函数<span class="arithmatex">\(f:A\to B\)</span>是双函数当且仅当存在函数<span class="arithmatex">\(g:B\to A\)</span>是的<span class="arithmatex">\(g\circ f=id_A\)</span>且<span class="arithmatex">\(f\circ g = id_B\)</span>，也就是说当且仅当其存在逆函数</p>
</li>
<li>
<p>（定义7.6）设函数<span class="arithmatex">\(f:A\to B\)</span>，若函数<span class="arithmatex">\(g:B\to A\)</span>满足<span class="arithmatex">\(g\circ f=id_A\)</span>则g是f的<strong>左逆</strong>，若函数<span class="arithmatex">\(g:B\to A\)</span>满足<span class="arithmatex">\(f\circ g=id_B\)</span>则g是f的<strong>右逆</strong></p>
</li>
<li>
<p>（定理7.4）设函数<span class="arithmatex">\(f:A\to B\)</span>且A非空，f是单函数当且仅当f存在左逆，f是满函数当且仅当f存在右逆</p>
</li>
</ul>
<h2 id="_6">函数的增长与算法效率分析</h2>
<h3 id="_7">函数的增长</h3>
<ul>
<li>（定义7.12）设f,g是两个数集上的函数，称f<strong>是O(g)</strong>，记为<span class="arithmatex">\(f\in O(g)\)</span>，如果存在常数<span class="arithmatex">\(C&gt;0\)</span>和<span class="arithmatex">\(k&gt;0\)</span>，使得当<span class="arithmatex">\(x&gt;k\)</span>时总有<span class="arithmatex">\(|f(x)\leq C|g(x)|\)</span>，这时常数C和k称为“函数f是O(g)”的见证</li>
</ul>
<div class="admonition note">
<p class="admonition-title">Note<p><span class="arithmatex">\(O(g)\)</span>其实是函数的集合</p>
</p>
</div>
<ul>
<li>（定理7.14）若f是O(g)，g是O(h)，则f是O(h)</li>
<li>（引理7.15）定义函数<span class="arithmatex">\(max(f,g)(x)=max(|f(x)|,|g(x)|)\)</span>，则当函数f和g都为O(h)时，max(f,g)也是O(h)</li>
<li>（定理7.16）若<span class="arithmatex">\(f_1\)</span>是<span class="arithmatex">\(O(g_1)\)</span>，<span class="arithmatex">\(f_2\)</span>是<span class="arithmatex">\(O(g_2)\)</span>，则<span class="arithmatex">\(f_1+f_2\)</span>是<span class="arithmatex">\(O(max(g_1,g_2))\)</span></li>
<li>（推论7.17）若<span class="arithmatex">\(f_1\)</span>是<span class="arithmatex">\(O(g)\)</span>，<span class="arithmatex">\(f_2\)</span>是<span class="arithmatex">\(O(g)\)</span>，则<span class="arithmatex">\(f_1+f_2\)</span>是<span class="arithmatex">\(O(g)\)</span></li>
<li>（定理7.18）若<span class="arithmatex">\(f_1\)</span>是<span class="arithmatex">\(O(g_1)\)</span>，<span class="arithmatex">\(f_2\)</span>是<span class="arithmatex">\(O(g_2)\)</span>，则<span class="arithmatex">\(f_1\cdot f_2\)</span>是<span class="arithmatex">\(O(g_1\cdot g_2)\)</span></li>
<li>（定义7.19）设f,g是两个数集上的函数，称f<strong>是</strong><span class="arithmatex">\(\Omega(g)\)</span>，记为<span class="arithmatex">\(f\in \Omega(g)\)</span>，如果存在常数<span class="arithmatex">\(C&gt;0\)</span>和<span class="arithmatex">\(k&gt;0\)</span>，使得当<span class="arithmatex">\(x&gt;k\)</span>时总有<span class="arithmatex">\(|f(x)\geq C|g(x)|\)</span>；称f是<span class="arithmatex">\(\Theta(g)\)</span>，记为<span class="arithmatex">\(f\in\Theta(g)\)</span>，如果<span class="arithmatex">\(f\in O(g)\)</span>并且<span class="arithmatex">\(f\in \Omega(g)\)</span>；如果f是<span class="arithmatex">\(\Theta(g)\)</span>，通常称f和g（在函数增长方面）有相同的<strong>阶</strong></li>
<li>（定理7.19）n次多项式是<span class="arithmatex">\(\Theta(x^n)\)</span>的</li>
<li>（定理7.20）若<span class="arithmatex">\(f_1\)</span>是<span class="arithmatex">\(O(g_1)\)</span>，<span class="arithmatex">\(f_2\)</span>是<span class="arithmatex">\(\Omega(g_2)\)</span>，且对于任意x，<span class="arithmatex">\(f_2(x)\neq 0\)</span>，则<span class="arithmatex">\(f_1/f_2\)</span>是<span class="arithmatex">\(O(g_1/g_2)\)</span></li>
</ul>
<h3 id="_8">算法效率分析基础</h3>
<ul>
<li>算法效率分为<strong>时间效率（时间复杂度）</strong>和<strong>空间效率（空间复杂度）</strong></li>
<li>算法效率分析对不同的输入分<strong>最坏情况</strong>、<strong>最好情况</strong>和<strong>平均情况</strong></li>
<li>时间效率分析框架<ol>
<li>确定哪个或哪些算法输入作为效率分析的依据，并确定如何度量输入规模</li>
<li>确定算法的基本操作</li>
<li>分别研究算法关于不同输入对需要执行的基本操作次数的函数的上界/下界</li>
</ol>
</li>
</ul>
<h3 id="_9">算法复杂度基础知识</h3>
<ul>
<li>常见的算法复杂度分类及典型算法</li>
</ul>
<table>
<thead>
<tr>
<th>复杂度</th>
<th>名称</th>
<th>可能的典型算法例子</th>
</tr>
</thead>
<tbody>
<tr>
<td><span class="arithmatex">\(\Theta(1)\)</span></td>
<td>常数</td>
<td>不包括循环和递归的算法</td>
</tr>
<tr>
<td><span class="arithmatex">\(\Theta(\log n)\)</span></td>
<td>对数</td>
<td>二分查找</td>
</tr>
<tr>
<td><span class="arithmatex">\(\Theta(n)\)</span></td>
<td>线性</td>
<td>线性查找</td>
</tr>
<tr>
<td><span class="arithmatex">\(\Theta(n\log n)\)</span></td>
<td>线性对数</td>
<td>许多分治算法</td>
</tr>
<tr>
<td><span class="arithmatex">\(\Theta(n^2)\)</span></td>
<td>平方</td>
<td>二重循环</td>
</tr>
<tr>
<td><span class="arithmatex">\(\Theta(n^3)\)</span></td>
<td>立方</td>
<td>三重循环</td>
</tr>
<tr>
<td><span class="arithmatex">\(\Theta(n^b)\)</span></td>
<td>多项式</td>
<td>基于逻辑积计算传递闭包</td>
</tr>
<tr>
<td><span class="arithmatex">\(\Theta(b^n)\)</span></td>
<td>指数</td>
<td>求幂集</td>
</tr>
<tr>
<td><span class="arithmatex">\(\Theta(n!)\)</span></td>
<td>阶乘</td>
<td>求所有排列组合</td>
</tr>
</tbody>
</table>
<ul>
<li>通常将最坏情况下存在复杂度为多项式的算法进行求解的问题称为<strong>易解问题</strong>，否则称为<strong>非易解问题</strong>；不可计算的问题称为<strong>不可解问题</strong></li>
<li>易解问题又称为<strong>N问题</strong>，在多项式复杂度内能判断一个候选解是否为真解的问题称为<strong>NP问题</strong>，<strong>NP完全问题（NPC问题）</strong>是所有NP问题都可以被归结为该问题的问题。命题逻辑公式的可满足性问题是一个NPC问题</li>
</ul>
              
            </div>
          </div><footer>
    <div class="rst-footer-buttons" role="navigation" aria-label="Footer Navigation">
        <a href="../6-%E5%85%B3%E7%B3%BB/" class="btn btn-neutral float-left" title="关系"><span class="icon icon-circle-arrow-left"></span> Previous</a>
        <a href="../8-%E8%AE%A1%E6%95%B0%E4%B8%8E%E7%BB%84%E5%90%88/" class="btn btn-neutral float-right" title="计数与组合">Next <span class="icon icon-circle-arrow-right"></span></a>
    </div>

  <hr/>

  <div role="contentinfo">
    <!-- Copyright etc -->
  </div>

  Built with <a href="https://www.mkdocs.org/">MkDocs</a> using a <a href="https://github.com/readthedocs/sphinx_rtd_theme">theme</a> provided by <a href="https://readthedocs.org">Read the Docs</a>.
</footer>
          
        </div>
      </div>

    </section>

  </div>

  <div class="rst-versions" role="note" aria-label="Versions">
  <span class="rst-current-version" data-toggle="rst-current-version">
    
    
      <span><a href="../6-%E5%85%B3%E7%B3%BB/" style="color: #fcfcfc">&laquo; Previous</a></span>
    
    
      <span><a href="../8-%E8%AE%A1%E6%95%B0%E4%B8%8E%E7%BB%84%E5%90%88/" style="color: #fcfcfc">Next &raquo;</a></span>
    
  </span>
</div>
    <script>var base_url = '../..';</script>
    <script src="../../js/theme_extra.js" defer></script>
    <script src="../../js/theme.js" defer></script>
      <script src="../../javascripts/mathjax.js" defer></script>
      <script src="https://fastly.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js" defer></script>
      <script src="../../search/main.js" defer></script>
    <script defer>
        window.onload = function () {
            SphinxRtdTheme.Navigation.enable(true);
        };
    </script>

</body>
</html>
